package com.leetcode.doublepoint;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * SumResolve..
 *
 * @author Lizhong
 * @date 2019/9/9
 */
public class SumResolve {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);
        int len = nums.length;
        int i = 0, j = len - 1, k;
        List list0 = new ArrayList();
        while ( i < len - 2) {
            if(nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) {
                i++;
                continue;
            }
            j = i + 1;
            k = len - 1;
            while (j < k) {
                int temp = nums[i] + nums[j] + nums[k];
                if (temp == 0) {
                    list0.add(Arrays.asList(nums[i],  nums[j],  nums[k]));
                    while (j < k && nums[k] == nums[--k]) ;
                    while (j < k && nums[j] == nums[++j]) ;
                } else if (temp > 0) {
                    while (j < k && nums[k] == nums[--k]) ;
                } else {
                    while (j < k && nums[j] == nums[++j]) ;

                }
            }
            i++;
        }
        return list0;
    }

    /**
     * 四个数相加
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len =nums.length;
        int a,b,c,d;
        a=0;

        Arrays.sort(nums);
        List list0=new ArrayList();

        for (;a<len-3;a++){
            if(a>0 && nums[a]==nums[a-1]) continue;

            int s=nums[a]+nums[a+1]+nums[a+2]+nums[a+3];
            int l=nums[a]+nums[len-3]+nums[len-2]+nums[len-1];
            if(s>target ) break;
            if(l<target ) continue;

            for(b=a+1;b<len-2;b++){
                if(b>a+1&&nums[b]==nums[b-1] ) continue;

                s=nums[a]+nums[b]+nums[b+1]+nums[b+2];
                l=nums[a]+nums[len-3]+nums[len-2]+nums[len-1];
                if(s>target ) break;
                if(l<target ) continue;
                c=b+1;
                d=len-1;
                while(c<d){
                    int x=nums[a]+nums[b]+nums[c]+nums[d];
                    if(x==target){
                        list0.add( Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
                        while(c<d && nums[c]==nums[++c]);
                        while (c<d && nums[d]==nums[--d]);
                    }else if(x<target){
                        while(c<d && nums[c]==nums[++c]);
                    } else{
                        while (c<d && nums[d]==nums[--d]);
                    }
                }
            }
        }
        return list0;
    }
    public static void main(String[] args) {
        SumResolve sumResolve = new SumResolve();
       int [] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = sumResolve.threeSum(nums);
        lists.forEach(val->val.forEach(System.out::println));


    }
}
